A $k$-coloring of a graph $G=(V,E)$ is called semi-equitable if there existsa partition of its vertex set into independent subsets $V_1,\ldots,V_k$ in sucha way that $|V_1| \notin \{\lceil |V|/k\rceil, \lfloor |V|/k \rfloor\}$ and$||V_i|-|V_j|| \leq 1$ for each $i,j=2,\ldots,k$. The color class $V_1$ iscalled non-equitable. In this note we consider the complexity of semi-equitable$k$-coloring, $k\geq 4$, of the vertices of a cubic or subcubic graph $G$. Inparticular, we show that, given a $n$-vertex subcubic graph $G$ and constants$\epsilon > 0$, $k \geq 4$, it is NP-complete to obtain a semi-equitable$k$-coloring of $G$ whose non-equitable color class is of size $s$ if $s \geqn/3+\epsilon n$, and it is polynomially solvable if $s \leq n/3$.
展开▼
机译：图$ G =（V，E）$的$ k $着色如果存在其顶点集的一部分划分为独立子集$ V_1，\ ldots，V_k $，则将其称为$ | V_1 | \ notin \ {\ lceil | V | / k \ rceil，\ lfloor | V | / k \ rfloor \} $和$ || V_i |-| V_j ||每个$ i，j = 2，\ ldots，k $ \ leq 1 $。颜色类别$ V_1 $被称为不平等的。在本说明中，我们考虑了三次或三次三次图形$ G $的顶点的半等值$ k $着色的复杂度$ k \ geq 4 $。特别地，我们表明，给定一个$ n $-顶点次三次图$ G $和常量$ \ epsilon> 0 $，$ k \ geq 4 $，获得半等价的$ k $着色是NP完全的。的$ G $，如果$ s \ geqn / 3 + \ epsilon n $，其不可替代的颜色类别的大小为$ s $，而如果$ s \ leq n / 3 $，则可以多项式求解。
展开▼
